package com.kaizen.leet169;

import java.util.HashMap;
import java.util.Map;

/**
 * @author undi
 *
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 示例 1:
 *
 * 输入: [3,2,3]
 * 输出: 3
 * 示例 2:
 *
 * 输入: [2,2,1,1,1,2,2]
 * 输出: 2
 * 通过次数163,596提交次数258,919
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/majority-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SolutionUndi {
    public static void main(String[] args) {
        int[] nums = new int[]{2,2,1,1,1,2,2,2,2,2};
        System.out.println(majorityElement(nums));
    }

    /**
     * 思路1：使用 hashMap 存放统计到的次数
     * 然后用 entry 遍历，拿到最大值的key，返回
     *
     * 执行结果：
     * 通过
     * 执行用时 :
     * 18 ms 在所有 Java 提交中击败了
     * 24.74%
     * 的用户
     * 内存消耗 :
     * 45.2 Mb, 在所有 Java 提交中击败了5.71%的用户
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        //统计个数
        //创建HashMap，key为数组中的值，value为值重复出现的次数
        Map<Integer,Integer> map = new HashMap<>(16);
        for(int i=0;i<nums.length;i++){
            //通过map.get()方法，获取map中是否已经存在该值，如果存在则通过key取到value并加一，否则key值为1
            map.put(nums[i], map.get(nums[i]) == null?1:map.get(nums[i])+1);
        }

        //使用推荐的遍历方法遍历Map，首先创建一个空的MapEntry键值对，
        // 如果遍历的值大于存放的entry，替换他，知道找出最大的value，返回key
        Map.Entry<Integer, Integer> mapEntry = null;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (mapEntry == null || entry.getValue() > mapEntry.getValue()) {
                mapEntry = entry;
            }
        }

        return mapEntry.getKey();
    }
}
